//最长有效括号
class Solution {
public:
    int longestValidParentheses(string s) 
    {
        int res=0;
        if(s.empty()) return res;
        stack<int>st;
        //栈顶始终发着的是 上一个没有匹配的)的下标！
        //避免当一开始就是 ()时 由于先pop()导致栈为空 又使用了top()函数导致报错
        st.push(-1);
        for(int i=0 ;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                st.push(i);
            }
            else
            {
                st.pop();
                //计算当前i和上一个没有被使用的)之间的距离
                if(!st.empty()) //栈不为空
                {
                    res=max(res,i-st.top());
                }
                else
                {
                    st.push(i);//目的是做一个起始下标 计算长度
                }
            }

        }
        return res;
    }
};

//下一个排列
class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        int i=0;
        for(i=nums.size()-2;i>=0;i--)
        {
            if(nums[i]<nums[i+1])
            {
                //          i  i+1
                // 1 2 3 8  5   7  6  4
                break;
            }
        }
        if(i==-1) reverse(nums.begin(),nums.end());
         //在i到后面中 选一个最小的但是大于i+1的
        else
        {
            for(int j=nums.size()-1;j>i;j--)
            {
                if(nums[j]>nums[i])
                {
                    swap(nums[j],nums[i]);
                    //         i i+1  j
                    // 1 2 3 8 6  7   5  4
                    // 1 2 3 8 6 已经比 1 2 3 8 5 大了 后面的需要是最小的
                    reverse(nums.begin()+i+1,nums.end());
                    break;
                }
                
            }
        }

    }
};
